\chapter{Section IV: Haskell and You}

\section{Part I: Where Are the 'For' Loops?}
As you may have noticed, the aren't any 'for' loops in Haskell. You could write them using IO monad functions, but I said that wasn't the right thing to do. So where are they? If you've already figured Haskell out, you can skip this section, but for those you like me that needed a lot of assistance, read on.

'for' loops are unnecessary. Not just in Haskell, but in general. The only reason that you have ever used 'for' loops is that you had to 'do' something to a chunk of memory to store the right value in the right spot. Haskell frees you from this, and when you got lost and wonder where your 'for' loops are, check here:

\begin{verbatim}
bar :: Int -> Int
bar = ...
    
foo :: [Int] -> [Int]
foo (x:xs) = bar x : foo xs
foo [] = []
\end{verbatim}

That looks a little too easy, and is actually equivalent to 'foo = map bar'. Here's a less contrived example. What if you were implementing a physics simulation, gravity for example, and you needed to calculate a new position of each object based on the other objects' positions? The following function calculates part of the process, which is finding, for each object, the sum of its mass times another object's mass divided by distance, over all other objects. In C, this would be accomplished by a pair of nested for loops, the outer one reading the mass and position from an array of objects, and the inner one computing mass1 times mass2 over the distance and summing it. Here are the types for that operation in Haskell:

\begin{verbatim}
type Mass = Double
type Pos = (Double, Double, Double) --x, y, z
type Obj = (Mass, Pos)

{-
Takes a list of objects.
Returns a list of (object, sum of mass times other object mass over distance for all objects)
Order is preserved.
-}

calcMassesOverDists :: [Obj] -> [Double]
\end{verbatim}

That's definitely the setup. '--' indicated that the rest of the line is a comment. '\{-' and '-\}' open and close block comments.

\begin{verbatim}
calcMassesOverDists objs = calcHelper objs objs

distXYZ :: Pos -> Pos -> Double
distXYZ (x1, y1, z1) (x2, y2, z2) = sqrt (xd * xd  + yd * yd + zd * zd)
    where
    (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2)

calcHelper :: [Obj] -> [Obj] -> [Double]
calcHelper (obj:objs) objList   = (sum (calcMMoD obj objList)) : calcHelper objs objList
calcHelper [] _ = []

calcMMoD :: Obj -> [Obj] -> [Double]
calcMMoD obj@(m1, pos1) ((m2, pos2):rest)   =  safeValue : calcMMoD obj rest
    where
    dist = distXYZ pos1 pos2
    safeValue = if pos1 == pos2 then 0 else m1 * m2 / dist
calcMMoD _ [] = []
\end{verbatim}

Okay, I threw something extra in there, too. 'obj@' in front of '(m1, pos1)'. The '@' is read 'as', and it means that 'obj' will refer to the whole value of type 'Obj', while '(m1, pos1)' will pattern match against the values in 'obj'. It's handy, because otherwise I would have to write '(m1, pos1)' again when I called 'calcMMoD' recursively, and I might make a typo when I did. Also, it's clearer. Note also that I did not have to completely 'take apart' obj. I left the value of type 'Pos' bound to 'pos1'. And note that I put all the sub-computations for 'distXYZ' into one line to save space. I defined the tuple '(x1 - x2, y1 - y2, z1 - z2)', and then bound it to the pattern of '(xd, yd, zd)', thus defining 'xd', 'yd', and 'zd' how I needed to. Finally note that dist is not evaluated in a call to calcMMoD if pos1 == pos2, and neither is m1 * m2 / dist, which avoids the division by zero.

I can compare equality between pos1 and pos2 because a tuple of types which are all in the class 'Eq' is also in the class 'Eq'. The definitions allowing that are here, although you have to scroll down about four pages:

\href{http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t%3AEq}{Prelude, Section: the Eq class}

What you're looking for is a line like this:

\begin{verbatim}
(Eq a, Eq b) => Eq (a, b)
\end{verbatim}

When listed in the 'Instances' section of the Eq class, that means that somewhere in the source code for the Prelude, there is an instance of Eq defined for '(a, b)' with the condition that both a and b are also members of Eq. The definition of that instance is fairly straightforward; the point is that it is there.

'sqrt' is a class function, and is defined (separately) for all types in the class 'Floating', which of course includes 'Double'. The type of 'sqrt' can be found here:

\href{http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#13}{Prelude, Section: the Floating class}

'sum' is a polymorphic function, and is defined (once) for all types in the class 'Num', which also of course includes 'Double'. The type of 'sum' can be found here:

\href{http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#13}{Prelude, Section: Special Folds}

I could have had calcMMoD return the sum, but code will compile to a more efficient result if the tasks are broken up, since 'sum' in the prelude is based on a tail-recursive and highly optimized function. The definition of 'sum' is in the Prelude, and more about 'tail recursion' can hopefully be found here:

\href{http://en.wikipedia.org/wiki/Tail\_recursion}{http://en.wikipedia.org/wiki/Tail\_recursion}

So where are the 'for' loops? Each recursive function iterates over a list, and the two together act as a nested pair of 'for' loops. This code is good, but there is a quicker way to write 'calcMassesOverDists' and 'calcMMoD', with the same types, and using a much simpler helper function for 'calcMMod':

\begin{verbatim}
calcMassesOverDists :: [Obj] -> [Double]
calcMassesOverDists objList = map (\obj -> sum (calcMMod obj objList)) objList
    
calcMMoD :: Obj -> [Obj] -> [Double]
calcMMoD obj objList = map (mMoDHelper obj) objList
    
mMoDHelper :: Obj -> Obj -> Double
mMoDHelper (m1, pos1) (m2, pos2) = if pos1 == pos2 then 0 else m1 * m2 / distXYZ pos1 pos2
    
distXYZ :: Pos -> Pos -> Double
distXYZ (x1, y1, z1) (x2, y2, z2) = sqrtDouble (xd * xd  + yd * yd + zd * zd)
    where
    (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2)
\end{verbatim}

I could have also avoided writing 'mMoDHelper' by using a lambda function:

\begin{verbatim}
calcMassesOverDists :: [Obj] -> [Double]
calcMassesOverDists objList = map (\obj -> sum (calcMMod obj objList)) objList
    
calcMMoD :: Obj -> [Obj] -> [Double]
calcMMoD (m1, pos1) objList = map (\(m2, pos2) -> if pos1 == pos2 then 0 else m1 * m2 / distXYZ pos1 pos2) objList
    
distXYZ :: Pos -> Pos -> Double
distXYZ (x1, y1, z1) (x2, y2, z2) = sqrtDouble (xd * xd  + yd * yd + zd * zd)
    where
    (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2)
\end{verbatim}

Or I could have avoided writing calcMMoD, but at that point it gets ridiculous:

\begin{verbatim}
calcMassesOverDists :: [Obj] -> [Double]
calcMassesOverDists objList = map
    (\obj1@(m1, pos1) -> sum (map (\(m2, pos2) -> if pos1 == pos2 then 0 else m1 * m2 / distXYZ pos1 pos2) objList) )
    objList

distXYZ :: Pos -> Pos -> Double
distXYZ (x1, y1, z1) (x2, y2, z2) = sqrtDouble (xd * xd  + yd * yd + zd * zd)
    where
    (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2)
\end{verbatim}

In any case, the division by zero will not be evaluated if pos1 == pos2. In the first example, note that mMoDHelper starts with a lowercase letter as all functions and variables do. Also note that none of these take much code to write. Haskell is like that. mMoDHelper is partially applied in this example. It is given only one of its two parameters where it is written in calcMMoD. The type of 'mMoDHelper obj' in that expression is:

\begin{verbatim}
mMoDHelper obj :: Obj -> Double
\end{verbatim}

This in turn is suitable as a parameter to 'map', as it only takes one parameter, rather than two.

Not every instance of a for loop should be turned into a 'map'. In this case, there is the Prelude function 'sum', which will take the list generated by the 'map' in calcMMoD and return the sum of its values. There is not always a pre-built function for your purposes. List functions are part of Haskell's core tools, and there are more advanced functions to use when you need them, such as 'foldr' and its variants.

Learning how to use 'foldr' and 'foldl' is a rite of passage for Haskell programmers. You will learn in time, by studying their definitions (in the Prelude) and definitions of other functions defined in terms of 'foldr' and 'foldl', such as (oddly enough) 'map'. For loops were just the beginning. When you get away from sequential behavior, real power comes out. Also, keep in mind that since foldr and map are used everywhere, GHC has heavily optimized them, and functions like them, so it's a good idea to use them.

\section{Part II: Remember Lazy Evaluation? It's Still There}

This section fleshes out the flexibility of the Haskell type system in a way that I haven't seen described for newcomers before. Hopefully, your are at least familiar with the concept of a 'Tree', that is, a data structure which has nodes that contain values and may also point to further nodes in the structure. 'Binary Trees' are one of the common forms, i.e. trees where each node has at most two children. For those of you for whom this is new, note this isn't a graph. Trees aren't supposed to loop back on themselves; they just branch. Anyway, here's my example.

\begin{verbatim}
data Tree a = Null | Node a (Tree a) (Tree a)
\end{verbatim}

This is a relatively complicated type. It is a 'data' type, defined with the reserved word 'data', like 'Maybe a' was. It is also polymorphic like 'Maybe a'; you can tell because the type, 'Tree a', takes a type variable. It has two data constructors, 'Null' and 'Node'. 'Null' has no arguments and 'Node' has three. The way it is named indicates that it is a tree, and on inspection it is a binary tree, having two children in 'Node'. So how would this work? First, let's write a value of this type:

\begin{verbatim}
t :: Tree Int
t = Node 3 (Node 2 Null Null) (Node 5 (Node 4 Null Null) Null)
\end{verbatim}

If we were to graph this tree, not including Null branches, it would look like this:

\begin{verbatim}
    3
   / \
  2   5
     /
    4
\end{verbatim}

The first node has both a 'left' child and a 'right' child, and the 'right' child of the first node also has a 'left' child. Let us review 'constructors'. In this example 'Tree a' is a type, and 'Node' and 'Null' are 'data constructors' for that type. A data constructor, often simply called a constructor, acts like a function that groups together objects to form an object of a datatype. They only exist for types defined using 'data' or 'newtype'. Note that they are different from type constructors, such as IO and Maybe. Data constructors act like functions, and do not belong in type signatures. Type constructors act like functions on types, and only belong in type signatures. They do not live in the same namespace, so often a 'data' type will have a data constructor of the same name out of convenience.

Constructors are also used to 'deconstruct' objects of 'data' types, like so:

\begin{verbatim}
inOrderList :: Tree a -> [a]
inOrderList Null    = []
inOrderList (Node item left right)  =
    inOrderList left ++ [item] ++ inOrderList right
\end{verbatim}

'inOrderList' uses pattern matching to determine which constructor its parameter uses. Further, it 'deconstructs' a value that uses the constructor 'Node' and binds its member values to the variables 'item', 'left', and 'right', which are of types 'a', 'Tree a', and 'Tree a', respectively. We know these types because Node's definition reads, "Node a (Tree a) (Tree a)", and 'a' is not further specified in this example. For those of you unfamiliar with trees, 't' above is a 'binary search tree', and evaluating 'inOrderList t' will result in the following:

\begin{verbatim}
inOrderList t
= [2, 3, 4, 5]
\end{verbatim}

Those values are in ascending order, since that is the definition of a 'binary search tree'. Read up on them if you're not familiar with them already.

There's another funny thing about the definition of 'Tree a'. It's recursive. It used 'Tree a' to define each child. You can do that in Haskell as well as C, but as usual, there's a twist, and again as usual it involves lazy evaluation. In C/C++, to use a type in its own definition, you must declare a pointer to an object of its type rather than including it directly. In Haskell, pointers aren't used like that, so the type is included directly, as in the tree example. So what about this definition:

\begin{verbatim}
foo :: Int -> Tree Int
foo n = Node n (foo (n - 1)) (foo (n + 1))
    
t2 = foo 0
\end{verbatim}

What is the value of 't2'? And what is its type? The value of 't2' requires an infinite amount of space to store. The first few levels of the trees could be drawn like this:

\begin{verbatim}
         0
       /   \
    -1       1
    / \     / \
  -2   0   0   2
  / \ / \ / \ / \
\end{verbatim}

And so on. But the type of 't2' is simple, and should be clear from the type of 'foo':

\begin{verbatim}
t2 :: Tree Int
\end{verbatim}

If you ever get an error message (not if ever, but when you get an error message) that says "can't do such-and-such, unification would result in infinite type", it means that the type would require an infinite amount of space to store. Typically this happens with pattern matching on lists. In that case a careful check will show that something incorrect in the code would have resulted in nested lists infinitely deep, meaning a type that looks like this:

\begin{verbatim}
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[....
\end{verbatim}

And so on. But back to 't2'. Its type is not infinite, even though its type is defined recursively and has a value that, when evaluated, would require infinite space to store. Because its type is defined recursively, Haskell (and you) know that values of type 'Tree a' can contain other values of type 'Tree a'. The fact that each value of type Tree a which is 'in' t2 uses the constructor 'Node' is not stored in the type of t2, so the type of t2 is finite and Haskell can use it. Also, multiple values of type 'Tree Int' can exist, some infinite, some not, and they all have the same type. Okay?

\section{Part III: The Point(s)}

I wrote all this about types to drive two points home. First, Haskell uses lazy evaluation. For example, the following type is valid and Haskell will not complain about it:

\begin{verbatim}
data Forever a = AThing a (Forever a)
\end{verbatim}

It is a polymorphic type, it has a single constructor 'AThing', and it is recursive. Values of this type will always be infinite if fully evaluated. That's okay, and you could use this in a program if you wanted to. Haskell would not attempt to fully evaluate an object of this type unless you told it to.

The second point is that learning and using Haskell requires unlearning and rethinking the basic assumptions most coders have developed about programming. Unlike so many languages, Haskell is not 'a little different', and will not 'take a little time'. It is very different and you cannot simply pick it up, although I hope that this tutorial will help.

If you play around with Haskell, do not merely write toy programs. Simple problems will not take advantage of Haskell's power. Its power shines mostly clearly when you use it to attack difficult tasks. Once Haskell's syntax is familiar to you, write programs that you would ordinarily think of as too complicated. For instance, implement graph-spanning algorithms and balanced-tree data types. At first, you'll probably trudge ahead using 'imperative thought processes'. As you work, you'll hopefully see that Haskell's tools let you dramatically simplify your code.

A big tip is, "Don't use arrays." Most of the time, you need to access members of a list one at a time, in order. If that is the case, you do not need an array, and it would take you a lot of work to set one up. Use a list. If you are truly storing data that needs random access, still don't use arrays. Use lists and '!!'. When you need speed, then use arrays. Use Arrays, and then switch to IOArrays. But only use them if you actually need speed. Your class projects absolutely will not need arrays unless you are writing a game, or working on something for at least three months. Then, you might need fast random-access data. Maybe. Use lists.
